In countermeasures against tampering attacks, particularly replay attacks, on a large-capacity memory located off-chip (off-chip memory) and connected to a processor, security information necessary for integrity verification for blocks (memory blocks) constituting the memory (referred to as memory integrity verification) need to be derived from limited amount of on-chip security information for each memory block and for each rewritten version. As an approach to this issue, there is proposed a method called a Bonsai Merkle Tree (Rogers, 2007) in which a secret key for integrity verification used in calculation of a MAC verification value is generated based on a unique identifier for each data block and hierarchical counter values, and security information is managed efficiently by limiting the objects of integrity verification to the counter values and data.
In a case where counter values protected against tampering using a tree is applied to memory protection, if the number of writes to off-chip memory of memory blocks to be protected exceeds the size of a lower counter and the lower counter overflows, a counter value of an upper counter (upper counter value) under a parent block of the hierarchical tree has to be updated (incremented) and a MAC verification value has to be recalculated simultaneously for all data blocks having the upper counter value in common. This may cause degradation in throughput and responsiveness of the memory system. If, on the other hand, the size of counters is increased, the number of levels of a tree to be protected is increased exponentially, which may result in reduction in space efficiency of the memory.